package com.topcoder.srm488;

import java.util.ArrayList;

public class TheBoringStoreDivTwo {
	public String find(String John, String Brus) {
		String longest = "";
		
		for (int as=0; as<John.length()-1; as++) {
			for (int ae=as+1; ae<John.length(); ae++) {
				String p1 = John.substring(as, ae);
				
				for (int bs=ae; bs<John.length(); bs++) {
					for (int be=bs+1; be<=John.length(); be++) {
						String p2 = John.substring(bs, be);
						String A = ae-as >= be-bs? p1 : p2;
						String B = ae-as >= be-bs? p2 : p1;
						if (!A.startsWith(B)) continue;
						
						for (int cs=0; cs<Brus.length()-1; cs++) {
							for (int ce=cs+1; ce<Brus.length(); ce++) {
								String p3 = Brus.substring(cs, ce);
								
								for (int ds=ce; ds<Brus.length(); ds++) {
									for (int de=ds+1; de<=Brus.length(); de++) {
										String p4 = Brus.substring(ds, de);
										String C = ce-cs >= de-ds? p3 : p4;
										String D = ce-cs >= de-ds? p4 : p3;
										if (!C.endsWith(D)) continue;
										
										int t = A.length() - B.length();
										if (t != C.length() - D.length()) continue;
										
										if (A.substring(B.length()).equals(C.substring(0, t))) {
											String name = A + D;
											if (name.length() > longest.length() ||
												(name.length() == longest.length() && name.compareTo(longest) < 0)) {
												longest = name;
											}
										}
									}
								}
							}
						}
						
					}
				}
			}
		}
		
		return longest;
	}
	
	boolean better(String A, String B) {
		return (A.length() > B.length() || A.length() == B.length() && A.compareTo(B) < 0);
	}

	public String find2(String John, String Brus) {
	    // Instead of nesting Brus' loops inside John's loops, we will first save
	    // the found prefixes/sufixes/scommon/pcommon in some lists and then
	    // process the lists. This simplifies the code at the expense of some overhead
	    // it is of course possible to do a 8 depth nested loop instead. But that
	    // optimization is not necessary.
	    //
	    ArrayList<String> prefixes = new ArrayList<String>();
	    ArrayList<String> pcommon  = new ArrayList<String>();
	    ArrayList<String> suffixes = new ArrayList<String>();
	    ArrayList<String> scommon  = new ArrayList<String>();
	    	    
	    // Find the prefixes and pcommon for all possible pairs of
	    // non-overlapping substrings in John:
		for (int i=0; i < John.length(); i++)
			for (int j=i; j < John.length(); j++)
				for (int k=j+1; k < John.length(); k++)
					for (int l=k; l < John.length(); l++) {
						String A = John.substring(i, j + 1);
						String B = John.substring(k, l + 1);
						// We need B.length() to be >= A.length().
						if (A.length() > B.length()) {
							String tmp = A;
							A = B;
							B = tmp;
						}
						//We need A to be a prefix of B.
						if (!B.startsWith(A))
							continue;
				        // Save in the list.
						String prefix = A;
						String common = B.substring(A.length());
						prefixes.add(prefix);
						pcommon.add(common);
					}

	    // Find the suffixes and scommon for all possible pairs of
	    // non-overlapping substrings in Brus:
		for (int i=0; i < Brus.length(); i++)
			for (int j=i; j < Brus.length(); j++)
				for (int k=j+1; k < Brus.length(); k++)
					for (int l=k; l < Brus.length(); l++) {
						String C = Brus.substring(i, j + 1);
						String D = Brus.substring(k, l + 1);
						// We need D.length() to be >= C.length().
						if (C.length() > D.length()) {
							String tmp = C;
							C = D;
							D = tmp;
						}
						// and C must be a suffix of D.
						if (!D.endsWith(C))
							continue;
					    // Save them in the list:
						String suffix = C;
						String common = D.substring(0, D.length() - C.length());
						suffixes.add(suffix);
						scommon.add(common);
					}

		String res = "";
		// Try all combinations of (prefix, pcommon) x (suffix,scommon)
		// There are actually O(n<sup>8</sup>) of them.
        for (int i=0; i< pcommon.size(); i++) {
            for (int j=0; j< scommon.size(); j++) {
                // If pcommon is equal to scommon, the final string
                // is valid.
	            if( pcommon.get(i).equals( scommon.get(j) ) ) {
	                String prefix = prefixes.get(i);
	                String common = pcommon.get(i);
	                String suffix = suffixes.get(j);
	                
	                // If the string is better than the current result,
	                // save it.
	                if(better(prefix+common+suffix, res)) {
	                     res = prefix+common+suffix;
	                }
	            }
            }
        }
		return res;
	}
}
